home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Libraries / Berkeley DB 1.6 / btree / bt_open.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-18  |  12.0 KB  |  509 lines  |  [TEXT/????]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_open.c    8.1 (Berkeley) 6/4/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  * Implementation of btree access method for 4.4BSD.
  43.  *
  44.  * The design here was originally based on that of the btree access method
  45.  * used in the Postgres database system at UC Berkeley.  This implementation
  46.  * is wholly independent of the Postgres code.
  47.  */
  48.  
  49. #include <sys/param.h>
  50. #include <sys/stat.h>
  51.  
  52. #include <errno.h>
  53. #include <fcntl.h>
  54. #include <limits.h>
  55. #include <signal.h>
  56. #include <stdio.h>
  57. #include <stdlib.h>
  58. #include <string.h>
  59. #include <unistd.h>
  60.  
  61. #ifdef macintosh
  62. #include <sys/fcntl.h>
  63. #include <sys/errno.h>
  64. #endif
  65.  
  66. #define    __DBINTERFACE_PRIVATE
  67. #include <db.h>
  68. #include "btree.h"
  69.  
  70. static int byteorder __P((void));
  71. static int nroot __P((BTREE *));
  72. static int tmp __P((void));
  73.  
  74. /*
  75.  * __BT_OPEN -- Open a btree.
  76.  *
  77.  * Creates and fills a DB struct, and calls the routine that actually
  78.  * opens the btree.
  79.  *
  80.  * Parameters:
  81.  *    fname:    filename (NULL for in-memory trees)
  82.  *    flags:    open flag bits
  83.  *    mode:    open permission bits
  84.  *    b:    BTREEINFO pointer
  85.  *
  86.  * Returns:
  87.  *    NULL on failure, pointer to DB on success.
  88.  *
  89.  */
  90. DB *
  91. __bt_open(fname, flags, mode, openinfo)
  92.     const char *fname;
  93.     int flags, mode;
  94.     const BTREEINFO *openinfo;
  95. {
  96.     BTMETA m;
  97.     BTREE *t;
  98.     BTREEINFO b;
  99.     DB *dbp;
  100.     pgno_t ncache;
  101.     struct stat sb;
  102.     int machine_lorder, nr;
  103.  
  104.     t = NULL;
  105.  
  106.     /*
  107.      * Intention is to make sure all of the user's selections are okay
  108.      * here and then use them without checking.  Can't be complete, since
  109.      * we don't know the right page size, lorder or flags until the backing
  110.      * file is opened.  Also, the file's page size can cause the cachesize
  111.      * to change.
  112.      */
  113.     machine_lorder = byteorder();
  114.     if (openinfo) {
  115.         b = *openinfo;
  116.  
  117.         /* Flags: R_DUP. */
  118.         if (b.flags & ~(R_DUP))
  119.             goto einval;
  120.  
  121.         /*
  122.          * Page size must be indx_t aligned and >= MINPSIZE.  Default
  123.          * page size is set farther on, based on the underlying file
  124.          * transfer size.
  125.          */
  126.         if (b.psize &&
  127.             (b.psize < MINPSIZE || b.psize > MAX_PAGE_OFFSET + 1 ||
  128.             b.psize & sizeof(indx_t) - 1))
  129.             goto einval;
  130.  
  131.         /* Minimum number of keys per page; absolute minimum is 2. */
  132.         if (b.minkeypage) {
  133.             if (b.minkeypage < 2)
  134.                 goto einval;
  135.         } else
  136.             b.minkeypage = DEFMINKEYPAGE;
  137.  
  138.         /* If no comparison, use default comparison and prefix. */
  139.         if (b.compare == NULL) {
  140.             b.compare = __bt_defcmp;
  141.             if (b.prefix == NULL)
  142.                 b.prefix = __bt_defpfx;
  143.         }
  144.  
  145.         if (b.lorder == 0)
  146.             b.lorder = machine_lorder;
  147.     } else {
  148.         b.compare = __bt_defcmp;
  149.         b.cachesize = 0;
  150.         b.flags = 0;
  151.         b.lorder = machine_lorder;
  152.         b.minkeypage = DEFMINKEYPAGE;
  153.         b.prefix = __bt_defpfx;
  154.         b.psize = 0;
  155.     }
  156.  
  157.     /* Check for the ubiquitous PDP-11. */
  158.     if (b.lorder != BIG_ENDIAN && b.lorder != LITTLE_ENDIAN)
  159.         goto einval;
  160.  
  161.     /* Allocate and initialize DB and BTREE structures. */
  162.     if ((t = malloc(sizeof(BTREE))) == NULL)
  163.         goto err;
  164.     t->bt_fd = -1;            /* Don't close unopened fd on error. */
  165.     if ((t->bt_dbp = dbp = malloc(sizeof(DB))) == NULL)
  166.         goto err;
  167.     t->bt_bcursor.pgno = P_INVALID;
  168.     t->bt_bcursor.index = 0;
  169.     t->bt_stack = NULL;
  170.     t->bt_sp = t->bt_maxstack = 0;
  171.     t->bt_kbuf = t->bt_dbuf = NULL;
  172.     t->bt_kbufsz = t->bt_dbufsz = 0;
  173.     t->bt_lorder = b.lorder;
  174.     t->bt_order = NOT;
  175.     t->bt_cmp = b.compare;
  176.     t->bt_pfx = b.prefix;
  177.     t->bt_flags = 0;
  178.     if (t->bt_lorder != machine_lorder)
  179.         SET(t, B_NEEDSWAP);
  180.  
  181.     dbp->type = DB_BTREE;
  182.     dbp->internal = t;
  183.     dbp->close = __bt_close;
  184.     dbp->del = __bt_delete;
  185.     dbp->fd = __bt_fd;
  186.     dbp->get = __bt_get;
  187.     dbp->put = __bt_put;
  188.     dbp->seq = __bt_seq;
  189.     dbp->sync = __bt_sync;
  190.  
  191.     /*
  192.      * If no file name was supplied, this is an in-memory btree and we
  193.      * open a backing temporary file.  Otherwise, it's a disk-based tree.
  194.      */
  195.     if (fname) {
  196.         switch(flags & O_ACCMODE) {
  197.         case O_RDONLY:
  198.             SET(t, B_RDONLY);
  199.             break;
  200.         case O_RDWR:
  201.             break;
  202.         case O_WRONLY:
  203.         default:
  204.             goto einval;
  205.         }
  206.         
  207.         if ((t->bt_fd =
  208. #ifdef macintosh
  209.             open(fname, flags & __USE_OPEN_FLAGS)) < 0)
  210. #else
  211.             open(fname, flags & __USE_OPEN_FLAGS, mode)) < 0)
  212. #endif
  213.             goto err;
  214.  
  215.     } else {
  216.         if ((flags & O_ACCMODE) != O_RDWR)
  217.             goto einval;
  218.         if ((t->bt_fd = tmp()) == -1)
  219.             goto err;
  220.         SET(t, B_INMEM);
  221.     }
  222.  
  223. #ifndef macintosh
  224.     if (fcntl(t->bt_fd, F_SETFD, 1) == -1)
  225.         goto err;
  226. #endif
  227.  
  228.     if (fstat(t->bt_fd, &sb))
  229.         goto err;
  230.     if (sb.st_size) {
  231. #ifdef macintosh
  232.         nr = read(t->bt_fd, (char *) &m, sizeof(BTMETA));
  233. #else
  234.         nr = read(t->bt_fd, &m, sizeof(BTMETA));
  235. #endif
  236.         if (nr < 0)
  237.             goto err;
  238.         if (nr != sizeof(BTMETA))
  239.             goto eftype;
  240.  
  241.         /*
  242.          * Read in the meta-data.  This can change the notion of what
  243.          * the lorder, page size and flags are, and, when the page size
  244.          * changes, the cachesize value can change too.  If the user
  245.          * specified the wrong byte order for an existing database, we
  246.          * don't bother to return an error, we just clear the NEEDSWAP
  247.          * bit.
  248.          */
  249.         if (m.m_magic == BTREEMAGIC)
  250.             CLR(t, B_NEEDSWAP);
  251.         else {
  252.             SET(t, B_NEEDSWAP);
  253.             BLSWAP(m.m_magic);
  254.             BLSWAP(m.m_version);
  255.             BLSWAP(m.m_psize);
  256.             BLSWAP(m.m_free);
  257.             BLSWAP(m.m_nrecs);
  258.             BLSWAP(m.m_flags);
  259.         }
  260.         if (m.m_magic != BTREEMAGIC || m.m_version != BTREEVERSION)
  261.             goto eftype;
  262.         if (m.m_psize < MINPSIZE || m.m_psize > MAX_PAGE_OFFSET + 1 ||
  263.             m.m_psize & sizeof(indx_t) - 1)
  264.             goto eftype;
  265.         if (m.m_flags & ~SAVEMETA)
  266.             goto eftype;
  267.         b.psize = m.m_psize;
  268.         t->bt_flags |= m.m_flags;
  269.         t->bt_free = m.m_free;
  270.         t->bt_nrecs = m.m_nrecs;
  271.     } else {
  272.         /*
  273.          * Set the page size to the best value for I/O to this file.
  274.          * Don't overflow the page offset type.
  275.          */
  276.         if (b.psize == 0) {
  277.             b.psize = sb.st_blksize;
  278.             if (b.psize < MINPSIZE)
  279.                 b.psize = MINPSIZE;
  280.             if (b.psize > MAX_PAGE_OFFSET + 1)
  281.                 b.psize = MAX_PAGE_OFFSET + 1;
  282.         }
  283.  
  284.         /* Set flag if duplicates permitted. */
  285.         if (!(b.flags & R_DUP))
  286.             SET(t, B_NODUPS);
  287.  
  288.         t->bt_free = P_INVALID;
  289.         t->bt_nrecs = 0;
  290.         SET(t, B_METADIRTY);
  291.     }
  292.  
  293.     t->bt_psize = b.psize;
  294.  
  295.     /* Set the cache size; must be a multiple of the page size. */
  296.     if (b.cachesize && b.cachesize & b.psize - 1)
  297.         b.cachesize += (~b.cachesize & b.psize - 1) + 1;
  298.     if (b.cachesize < b.psize * MINCACHE)
  299.         b.cachesize = b.psize * MINCACHE;
  300.  
  301.     /* Calculate number of pages to cache. */
  302.     ncache = (b.cachesize + t->bt_psize - 1) / t->bt_psize;
  303.  
  304.     /*
  305.      * The btree data structure requires that at least two keys can fit on
  306.      * a page, but other than that there's no fixed requirement.  The user
  307.      * specified a minimum number per page, and we translated that into the
  308.      * number of bytes a key/data pair can use before being placed on an
  309.      * overflow page.  This calculation includes the page header, the size
  310.      * of the index referencing the leaf item and the size of the leaf item
  311.      * structure.  Also, don't let the user specify a minkeypage such that
  312.      * a key/data pair won't fit even if both key and data are on overflow
  313.      * pages.
  314.      */
  315.     t->bt_ovflsize = (t->bt_psize - BTDATAOFF) / b.minkeypage -
  316.         (sizeof(indx_t) + NBLEAFDBT(0, 0));
  317.     if (t->bt_ovflsize < NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t))
  318.         t->bt_ovflsize =
  319.             NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t);
  320.  
  321.     /* Initialize the buffer pool. */
  322.     if ((t->bt_mp =
  323.         mpool_open(NULL, t->bt_fd, t->bt_psize, ncache)) == NULL)
  324.         goto err;
  325.     if (!ISSET(t, B_INMEM))
  326.         mpool_filter(t->bt_mp, __bt_pgin, __bt_pgout, t);
  327.  
  328.     /* Create a root page if new tree. */
  329.     if (nroot(t) == RET_ERROR)
  330.         goto err;
  331.  
  332.     return (dbp);
  333.  
  334. einval:    errno = EINVAL;
  335.     goto err;
  336.  
  337. eftype:    errno = EFTYPE;
  338.     goto err;
  339.  
  340. err:    if (t) {
  341.         if (t->bt_dbp)
  342.             free(t->bt_dbp);
  343.         if (t->bt_fd != -1)
  344.             (void)close(t->bt_fd);
  345.         free(t);
  346.     }
  347.     return (NULL);
  348. }
  349.  
  350. /*
  351.  * NROOT -- Create the root of a new tree.
  352.  *
  353.  * Parameters:
  354.  *    t:    tree
  355.  *
  356.  * Returns:
  357.  *    RET_ERROR, RET_SUCCESS
  358.  */
  359. static int
  360. nroot(t)
  361.     BTREE *t;
  362. {
  363.     PAGE *meta, *root;
  364.     pgno_t npg;
  365.  
  366.     if ((meta = mpool_get(t->bt_mp, 0, 0)) != NULL) {
  367.         mpool_put(t->bt_mp, meta, 0);
  368.         return (RET_SUCCESS);
  369.     }
  370.     if (errno != EINVAL)
  371.         return (RET_ERROR);
  372.  
  373.     if ((meta = mpool_new(t->bt_mp, &npg)) == NULL)
  374.         return (RET_ERROR);
  375.  
  376.     if ((root = mpool_new(t->bt_mp, &npg)) == NULL)
  377.         return (RET_ERROR);
  378.  
  379.     if (npg != P_ROOT)
  380.         return (RET_ERROR);
  381.     root->pgno = npg;
  382.     root->prevpg = root->nextpg = P_INVALID;
  383.     root->lower = BTDATAOFF;
  384.     root->upper = t->bt_psize;
  385.     root->flags = P_BLEAF;
  386.     memset(meta, 0, t->bt_psize);
  387.     mpool_put(t->bt_mp, meta, MPOOL_DIRTY);
  388.     mpool_put(t->bt_mp, root, MPOOL_DIRTY);
  389.     return (RET_SUCCESS);
  390. }
  391.  
  392. #ifdef macintosh
  393. #include <Files.h>
  394. #include <Folders.h>
  395. #include <TFileSpec.h>
  396. #include <Errors.h>
  397.  
  398. typedef struct tfdsc {
  399.     struct tfdsc *    next;
  400.     FSSpec            spec;
  401. } tfdsc;
  402.  
  403. static tfdsc * tempdescs = 0;
  404.  
  405. static void closedescs()
  406. {
  407.     while (tempdescs) {
  408.         HDelete(tempdescs->spec.vRefNum, tempdescs->spec.parID, tempdescs->spec.name);
  409.         
  410.         tempdescs = tempdescs->next;
  411.     }
  412. }
  413.  
  414. /* Create a temporary file in the temp folder. 
  415. */
  416. static int tmp()
  417. {
  418.     static int    id    =    0;
  419.     FSSpec        desc;
  420.     OSErr            err;
  421.     tfdsc *        nudsc;
  422.     
  423.     if (err = FindFolder(kOnSystemDisk, 'temp', true, &desc.vRefNum, &desc.parID))
  424.         return -1;
  425.     
  426.     *((long *) desc.name)        =    '\007tmp';
  427.     
  428.     do {
  429.         desc.name[4]    =    id / 1000     % 10 + '0';
  430.         desc.name[5]    =    id / 100        % 10 + '0';
  431.         desc.name[6]    =    id / 10        % 10 + '0';
  432.         desc.name[7]    =    id             % 10 + '0';
  433.         
  434.         ++id;
  435.         
  436.         err = HCreate(desc.vRefNum, desc.parID, desc.name, 'TEMP', 'TEXT');
  437.     } while (err == dupFNErr);
  438.     
  439.     id = open(FSp2FullPath(&desc), O_RDWR);
  440.     
  441.     if (id < 0)
  442.         return id;
  443.     
  444.     if (!tempdescs)
  445.         atexit(closedescs);
  446.     
  447.     nudsc = malloc(sizeof(tfdsc));
  448.     
  449.     nudsc->next = tempdescs;
  450.     nudsc->spec = desc;
  451.     tempdescs     = nudsc;
  452.     
  453.     return id;
  454. }
  455. #else
  456. static int
  457. tmp()
  458. {
  459.     sigset_t set, oset;
  460.     int fd;
  461.     char *envtmp;
  462.     char path[MAXPATHLEN];
  463.  
  464.     envtmp = getenv("TMPDIR");
  465.     (void)snprintf(path,
  466.         sizeof(path), "%s/bt.XXXXXX", envtmp ? envtmp : "/tmp");
  467.  
  468.     (void)sigfillset(&set);
  469.     (void)sigprocmask(SIG_BLOCK, &set, &oset);
  470.     if ((fd = mkstemp(path)) != -1)
  471.         (void)unlink(path);
  472.     (void)sigprocmask(SIG_SETMASK, &oset, NULL);
  473.     return(fd);
  474. }
  475. #endif
  476.  
  477. static int
  478. byteorder()
  479. {
  480.     u_long x;            /* XXX: 32-bit assumption. */
  481.     u_char *p;
  482.  
  483.     x = 0x01020304;
  484.     p = (u_char *)&x;
  485.     switch (*p) {
  486.     case 1:
  487.         return (BIG_ENDIAN);
  488.     case 4:
  489.         return (LITTLE_ENDIAN);
  490.     default:
  491.         return (0);
  492.     }
  493. }
  494.  
  495. int
  496. __bt_fd(dbp)
  497.         const DB *dbp;
  498. {
  499.     BTREE *t;
  500.  
  501.     t = dbp->internal;
  502.  
  503.     if (ISSET(t, B_INMEM)) {
  504.         errno = ENOENT;
  505.         return (-1);
  506.     }
  507.     return (t->bt_fd);
  508. }
  509.